#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

class Lru
{
public:
    Lru(size_t capa)
        :_capacity(capa)
    {

    }

    void put(int key,int value)
    {
        //find返回的是迭代器，相当于指针
        //所以访问容器中的成员使用->
        auto it = _unmap.find(key);

        //1.先判断在不在list里面，如果数据存在
        //list不能使用下标，而且查找复杂度比较高
        //所以利用unordered_map<int,list<pair<int,int>>::iterator>
        //来存key值和对应的list迭代器
        //使用unordered_map容器查找key值，复杂度较低
        if(it != _unmap.end())
        {
            //更新value值
            it->second->second = value;
            //把元素移到list的头部
            _lst.splice(_lst.begin(),_lst,it->second);
        }
        //2.不在的情况下先判断容器是否为满
        else
        {
            if(_capacity == _lst.size())
            {
                //2.1容器满的情况下，需要删除list最后一个元素
                //删除unordered_map容器的最后一个元素
                //把{key，value}添加到list的头部
                //最后把新加入的数据放入unordered_map容器中
                auto itmap = _lst.back();//back返回的是最后一个元素
                _lst.pop_back();
                _unmap.erase(itmap.first);
                _lst.push_front({key,value});
                _unmap[key] = _lst.begin();
            }
            else
            {
                //2.容器不满的情况下，直接把数据添加到list的头部
                //然后把数据添加到unordered_map容器中
                _lst.push_front({key,value});
                _unmap[key] = _lst.begin();
            }
        }
    }

    int get(int key)
    {
        auto it = _unmap.find(key);
        if(it == _unmap.end())
        {
            return -1;
        }
        else
        {
            _lst.splice(_lst.begin(),_lst,it->second);
            return it->second->second;
        }
    }
    void print() const
    {
        for(auto &elem : _lst)
        {
            cout << "(" << elem.first
                 << "," << elem.second 
                 << ")" << " ";
        }
        cout << endl;
    }

private:
    size_t _capacity;
    list<pair<int,int>> _lst;
    unordered_map<int,list<pair<int,int>>::iterator> _unmap;
};


void test(){
    Lru lru(3);

    cout << endl;
    lru.put(1, 10);//(1, 10)
    lru.print();

    cout << endl;
    lru.put(2, 20);//(2, 20) (1, 10)
    lru.print();

    cout << endl;
    cout << "lru.get(1) = " << lru.get(1) << endl;//10
    lru.print();

    cout << endl;
    lru.put(3, 30);//(3, 30) (1, 10) (2, 20)
    lru.print();

    cout << endl;
    lru.put(4, 40);//(4, 40) (3, 30) (1, 10)
    lru.print();

    cout << endl;
    cout << "lru.get(2) = " << lru.get(2) << endl;//-1
    lru.print();

    cout << endl;
    lru.put(3, 33);
    lru.print();

    cout << endl;
    cout << "lru.get(1) = " << lru.get(1) << endl;//10
    lru.print();
}

int main()
{
    test();
    return 0;
}

